﻿/************************************************************
*
* 命名空间：Deep.Algorithm.Sorting
* 文件名称：StringBubbleSort.cs
* 创建者：王嘉庆
* 创建日期：2021-05-23 05:40:40
* 邮箱：1101202419@qq.com
* 博客：https://blog.csdn.net/wuxinwudai
* 功能描述：
* 使用说明：
* 最后更新日期：
*************************************************************/
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Deep.Algorithm.Sorting
{
    /// <summary>
    /// 字符串冒泡排序
    /// </summary>
    public class BubbleSort: SortAlgorithm
    {
        /// <summary>
        /// 字符串数组冒泡排序，按字母序列从a到z的顺序排列，是稳定算法，时间复杂度 O(n^2)
        /// </summary>
        /// <param name="arr">字符串数组</param>
        /// <returns></returns>
        public override T[] Sort<T>(T[] arr)
        {
            int i, j; //交换标志 
            T temp;
            bool exchange;
            for (i = 0; i < arr.Length; i++) //最多做R.Length-1趟排序 
            {
                exchange = false; //本趟排序开始前，交换标志应为假 
                for (j = arr.Length - 2; j >= i; j--)
                {//交换条件 
                    if (arr[j + 1].CompareTo(arr[j]) < 0)
                    {
                        temp = arr[j + 1];
                        arr[j + 1] = arr[j];
                        arr[j] = temp;
                        exchange = true; //发生了交换，故将交换标志置为真 
                    }
                }
                if (!exchange) //本趟排序未发生交换，提前终止算法 
                {
                    break;
                }
            }
            return arr;
        }
    }
}
